class Solution {
    public:
        string path;
        vector<string> v;
        unordered_map<char,string> m;
        void inithash(){
            m.insert(make_pair('2',"abc"));
            m.insert(make_pair('3',"def"));
            m.insert(make_pair('4',"ghi"));
            m.insert(make_pair('5',"jkl"));
            m.insert(make_pair('6',"mno"));
            m.insert(make_pair('7',"pqrs"));
            m.insert(make_pair('8',"tuv"));
            m.insert(make_pair('9',"wxyz"));
        }
        vector<string> letterCombinations(string digits) { 
            if(digits.size() == 0) return v;
            inithash();
            dfs(digits,0);
            return v;
        }
        void dfs(string nums,int i){
            if(i == nums.size()){
                v.push_back(path);
                return;
            }
            for(int k = 0 ; k < m[nums[i]].size() ; k++){
                path.push_back(m[nums[i]][k]);
                dfs(nums,i+1);
                path.pop_back();
            }
        }
    };